package com.java_foundation.arithmetic;

public class HeadSort {
    /**
     * 堆排序
     *
     * 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
     * 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
     * 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
     * @param nums  待排序数组
     */
    public void heapSort(int[] nums){
        int len = nums.length;
        for(int i = len; i > 0; i--){
            max_heapify(nums, i);

            int temp = nums[0];      //堆顶元素(第一个元素)与Kn交换
            nums[0] = nums[i-1];
            nums[i-1] = temp;
        }
    }

    public void max_heapify(int[] nums, int limit){
        int len = nums.length;
        if(len <= 0 || len < limit) return;
        int parentIdx = limit / 2;

        for(; parentIdx >= 0; parentIdx--){
            if(parentIdx * 2 >= limit){
                continue;
            }
            int left = parentIdx * 2;       //左子节点位置
            int right = (left + 1) >= limit ? left : (left + 1);    //右子节点位置，如果没有右节点，默认为左节点位置

            int maxChildId = nums[left] >= nums[right] ? left : right;
            if(nums[maxChildId] > nums[parentIdx]){   //交换父节点与左右子节点中的最大值
                int temp = nums[parentIdx];
                nums[parentIdx] = nums[maxChildId];
                nums[maxChildId] = temp;
            }
        }
    }
}
